package org.example.top40;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class main40_2 {
    public static void main(String[] args) {
        TreeNode root = builder();
        List<Integer> res = inorder(root);
        System.out.println(res);
    }

    private static List<Integer> inorder(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node!=null){
                stack.pop();
                if(node.right!=null){
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else {
                stack.pop();
                TreeNode cur = stack.pop();
                res.add(cur.val);
            }
        }
        return res;

    }

    private static TreeNode builder() {
        /**
         *       3
         *     9   20
         *        15  7
         */
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        return root;
    }
}
